1679D - Toss a Coin to Your Graph - CodeForces Solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<string>
#define pll pair<long long,long long>
#define F first
#define S second
typedef long long ll;
using namespace std;
vector<vector<ll> > gr;
vector<ll>colors;
vector<ll>topik;
bool cycl = 0;
vector<ll>a;
void dfs(ll v,ll wei)
{
	colors[v] = 1;
	for (auto f : gr[v])
	{
		if (a[f]<=wei&&colors[f] == 0)dfs(f,wei);
		else if (a[f]<=wei&&colors[f] == 1)cycl = 1;
	}
	colors[v] = 2;
}
void top_sort(ll v,ll wei)
{
	colors[v] = 1;
	for (auto f : gr[v])if (a[f]<=wei&&colors[f] == 0)top_sort(f,wei);
	topik.push_back(v);
}
vector<ll>d;
ll mx = -1e9;
void dfs3(ll v,ll wei)
{
	d[v] = 1;
	colors[v] = 1;
	for (auto y : gr[v])
	{
		if (a[y] <= wei)
		{
			if (colors[y] == 0)dfs3(y, wei);
			d[v] = max(d[v], d[y] + 1);
		}
	}
	mx = max(mx, d[v]);
}
int main()
{
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	ll n, m, k;
	cin >> n >> m >> k;
	a.resize(n);
	colors.resize(n, 0);
	gr.resize(n);
	for (ll i = 0; i < n; ++i)cin >> a[i];
	ll vf, vs;
	for (ll i = 0; i < m; ++i)
	{
		cin >> vf >> vs;
		--vf, --vs;
		gr[vf].push_back(vs);
	}
	ll r = 1e9+7, l = 0, mi;
	while (r - l > 1)
	{
		mi = (r + l) >> 1;
		cycl = 0;
		colors.assign(n, 0);
		for (ll i = 0; i < n; ++i)if (a[i] <= mi&&colors[i]==0)dfs(i, mi);
		if (cycl)
		{
			r = mi;
			continue;
		}
		colors.assign(n, 0);
		topik.clear();
		for (ll i = 0; i < n; ++i)if (a[i]<=mi&&colors[i] == 0)top_sort(i,mi);
		reverse(topik.begin(), topik.end());
		mx = -1e9;
		d.assign(n, 0);
		colors.assign(n, 0);
		for (ll i = 0; i <topik.size(); ++i)
		{
			if (colors[topik[i]] == 0)dfs3(topik[i], mi);
		}
		if (mx >= k)r = mi;
		else l = mi;
	}
	if (r > 1e9)cout << -1 << '\n';
	else cout << r << '\n';
	return 0;
}